/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hj3;

import java.util.ArrayList;

/**
 *ALGORITMOS Y ESTRUCTURA DE DATOS
 *HOJA DE TRABAJO 3
 * SECCION 10
 * 
 * ROGER DIAZ
 * YUCELY BEB
 * RODIMIRO CATAÑEDA
 * VICTOR FUETNES 12298
 * 
 */

//Metodos partition, swap, sort, y quickSortRecursive fueron tamados de:
//Bailey, D. 2007. Java Structures, Cap 9: Lists. Williams Collage. Estados Unidos de America. pp179.
public class QuickSort {
    //variables
    ArrayList<String> lista;//arraay de entrada desde main
    ArrayList<String> listaOrdenada;//array ya ordenada, usada para imprmir
    int largo;//largo de list, list usada para trabajo de metodos
    int list[];//lista para el manejo de los lementos
    int list2[];//lista ya ordenada usada para volver a ejectuar el algoritmos para comprobar tiempo
    //constructor
    public QuickSort(ArrayList h){
        listaOrdenada=new ArrayList<>();
        lista=h;
        largo=lista.size()-1;
        list=new int[largo+1];
        for(int a=0; a<=largo;a++){
            int id=0;
            id=Integer.parseInt(lista.get(a));
            
                    
            list[a]=id;
        }
        Sort(list,list.length);//metodo para ordenar
        
    }
    
    //metodo para copiar list a list2, list2 estara ya ordenada y entrada a exe2 para repetir algoritmo de orden
    public void copiarLista(){
        list2=new int[list.length];
        for(int i=0;i<list.length;i++){
            list2[i]=list[i];
        }
    }
    
    //metodo usado para volver a ejecutar el algoritmos de ordenamiento pero con lista ya ordenada
    public void EXE2(){
        Sort(list2,list.length);//en este punto list ya esta ordenada, volver a ejecutar algoritmo para comprobar tiempo
    }
    // \ <>
    private static int partition(int data[],int left,int right){
        while (true){
            //corrimiento hacia izquirda del puntero derecho
            while (left<right && data[left] < data[right]){
                right--;//se corre puntero derecho hacia izquirda
            }
            if(left<right){
                swap(data,left++,right);
            }else return left;
            
            //corrimiento hacia derecha del puntero izquierdo
            while(left<right && data[left] < data[right]){
                left++;//se corre puntero izquierdo a derecha
            }
            if(left<right){
                swap(data,left,right--);
            }else return right;
            
        }
    }
    
    //metodo swap, intercambio de posiciones
    public static void swap(int data[],int i, int j){
        int temp;
        temp=data[i];//almacenar elemento en temporal
        data[i]=data[j];//movoer desde j hasta i
        data[j]=temp;//rescribir j segun temp, o sea segun i
    }
    
    //se requiere lista con valores en orden ascendiente
    public static void Sort(int data[], int n){
        quickSortRecursive(data,0,n-1);
    }
    
    private static void quickSortRecursive(int data[],int left,int right){
        int pivote;//valor final del valor en la lista
        if(left>=right) return;
            pivote=partition(data,left,right);//se ajusta el pivote
            quickSortRecursive(data,left,pivote-1);//
            quickSortRecursive(data,pivote+1,right);
        
    }
    
    public int getLargo(){
        return largo;
    }
    
    public int getLargoList(){
        return list.length;
    }
            
    
    public void imprimirArrayDesordenado(){
        System.out.println(lista);
        
    }
    
    public String imprimirListOrdenado(){
        String salida="";
        for(int i=0; i<=largo;i++){
            salida+=list[i];
        }
        
        return salida;
        
    }
    
    public void Ordenada(){
        int i=list.length;
        String add="";
        for(int a=0;a<i;a++){
          
            add=Integer.toString(list[a]);
            listaOrdenada.add(add);
        }
    }
    
    public void imprimirArrayOrdenado(){
        System.out.println(listaOrdenada);
        System.out.println(listaOrdenada.size());
    }
    
    public String imprimirList2Ordenada(){
        int i=list2.length;
        String re="";
        for(int a=0;a<i;a++){
            re+=" "+list2[a]+",";
        }
        
        
        return re;
    }
}

